#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct Prod
{
	int w, v;
};

vector<Prod> *bag(vector<Prod> &prds,int W)
{
	vector<Prod> *list = new vector<Prod>;
	vector<vector<int>> V(prds.size(), vector<int>(W+1, 0));
	for (int j = 1; j < V[0].size(); ++j)
	{
		if (prds[0].w <= j)
			V[0][j] = prds[0].v;
	}

	for (int i = 1; i < V.size(); ++i)
	{
		for (int j = 1; j < V[i].size(); ++j)
		{
			if (prds[i].w < j)
			{
				int x = V[i - 1][j - prds[i].w] + prds[i].v, y = V[i - 1][j];
				V[i][j] = x>y ? x : y;
			}
		}
	}
	return list;
}


int main()
{
	vector<Prod> prd = { {2,6},{2,3},{6,5},{5,4},{4,6} };

	bag(prd, 10);
	return 0;
}